﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms
{
    public class GeneticAlgorithm
    {
        #region Constants

        public const double DefaultMutationRate = 0.05d;
        public const double DefaultCrossoverRate = 0.80d;
        public const int DefaultPopulationSize = 2000;

        #endregion // Constants

        #region Fields

        private double _mutationRate = DefaultMutationRate;
        private double _crossoverRate = DefaultCrossoverRate;
        private int _generationSize = DefaultPopulationSize;

        private Random _random = new Random();

        private IGeneticAlgorithmTarget _target;      
        private ISortingStrategy _sortingStrategy;

        #endregion // Fields

        #region Constructor

        /// <summary>
        /// Default constructor
        /// </summary>
        public GeneticAlgorithm(IGeneticAlgorithmTarget target, 
            ISortingStrategy sortingStrategy)
        {
            if (target == null)
                throw new ArgumentNullException("target");
            if (sortingStrategy == null)
                throw new ArgumentNullException("sortingStrategy");

            _target = target;
            _sortingStrategy = sortingStrategy;
        }

        #endregion // Constructor

        #region Properties

        public double MutationRate { get { return _mutationRate; } set { _mutationRate = value; } }
        public double CrossoverRate { get { return _crossoverRate; } set { _crossoverRate = value; } }
        public int GenerationSize { get { return _generationSize; } set { _generationSize = value; } }

        public bool IsWorking { get; protected set; }

        public int GenerationCount { get; set; }
        public double BestRanking { get; set; }
        public double AverageRanking { get; set; }

        #endregion // Properties

        #region Methods

        public void Reset()
        {
            GenerationCount = 0;
            AverageRanking = 0;
            BestRanking = 0;

            IsWorking = false;
        }

        public bool Work(out int[] result)
        {
            Reset();

            IsWorking = true;

            // define data
            IGeneticAlgorithmTarget target = _target;
            Genome[] currentGeneration;
            Genome[] nextGeneration;
            double[] currentGenerationFitness;

            int genomeLength = target.GenomeLength;

            // create initial genomes
            currentGeneration = new Genome[GenerationSize];
            nextGeneration = new Genome[GenerationSize];
            currentGenerationFitness = new double[GenerationSize];

            //Create the initial generation
            currentGeneration = CreateInitialGeneration();

            while (IsWorking)
            {
                GenerationCount++;
                UpdateStatistics(currentGenerationFitness);

                // Do the first ranking
                double totalFitness = RankGeneration(target, _sortingStrategy, currentGeneration, currentGenerationFitness);

                if (currentGenerationFitness[GenerationSize - 1] == 1)
                {
                    break;
                }

                // If we walked death, restart with a clean generation
                if (totalFitness == 0)
                {
                    currentGeneration = CreateInitialGeneration();
                }
                else
                {
                    // Create the next generation based on the current
                    CreateNextGeneration(nextGeneration, currentGeneration, currentGenerationFitness, totalFitness);

                    // and move next to current (so we dont have to put to much pressure on the GC)
                    Genome[] temp = currentGeneration;
                    currentGeneration = nextGeneration;
                    nextGeneration = temp;
                }
            }

            IsWorking = false;

            result = currentGeneration[GenerationSize - 1].Genes;

            return currentGenerationFitness[GenerationSize - 1] == 1;
        }

        #endregion // Methods

        #region Helpers

        protected void UpdateStatistics(double[] generation)
        {
            BestRanking = (100 / 1d) * generation[GenerationSize - 1];
            AverageRanking = generation.Average(x => (100 / 1d) * x);
        }

        protected Genome[] CreateInitialGeneration()
        {
            Genome[] generation = new Genome[GenerationSize];
            int genomeLength = _target.GenomeLength;

            for (int index = 0; index < GenerationSize; index++)
            {
                Genome nextGenome = new Genome(genomeLength);
                nextGenome.Scramble();

                generation[index] = nextGenome;
            }

            return generation;
        }

        protected Genome[] CreateNextGeneration(Genome[] nextGeneration, Genome[] currentGeneration, double[] currentGenerationFitness, double totalFitness)
        {   
            for (int index = 0; index < nextGeneration.Length; index += 2)
            {
                int parent1Index = RouletteSelection(_random, currentGenerationFitness, totalFitness);
                int parent2Index = RouletteSelection(_random, currentGenerationFitness, totalFitness);

                Genome child1;
                Genome child2;

                if (_random.NextDouble() > CrossoverRate)
                {
                    Genome parent1 = currentGeneration[parent1Index];
                    Genome parent2 = currentGeneration[parent2Index];

                    // virtually create 2 new offsprings by taking the offsprigns of the current generation and crossover them together
                    parent1.Crossover(parent2, out child1, out child2);
                }
                else
                {
                    child1 = currentGeneration[parent1Index];
                    child2 = currentGeneration[parent2Index];
                }

                // mutate the offsprings
                child1.Mutate(MutationRate);
                child2.Mutate(MutationRate);

                nextGeneration[index] = child1;
                nextGeneration[index + 1] = child2;
            }

            return nextGeneration;
        }

        /// <summary>
        /// After ranking all the genomes by fitness, use a 'roulette wheel' selection
        /// method.  This allocates a large probability of selection to those with the 
        /// highest fitness.
        /// </summary>
        /// <returns>Random individual biased towards highest fitness</returns>
        protected static int RouletteSelection(Random random, double[] fitnessTable, double totalFitness)
        {
            double slice = random.NextDouble() * totalFitness;
            double currentFitness = 0;

            for (int index = 0; index < fitnessTable.Length; index++)
            {
                currentFitness += fitnessTable[index];
                if (currentFitness >= slice)
                {
                    return index;
                }
            }

            throw new InvalidOperationException("We should not get here");
        }

        protected static double RankGeneration(IGeneticAlgorithmTarget target, ISortingStrategy sortingStrategy, Genome[] generation, double[] ranks)
        {
            double totalRanking = 0;

            //for (int index = 0; index < generation.Length; index++)
            //{
            //    Genome genome = generation[index];
            //    double rank = target.CalculateFitness(genome.Genes);

            //    totalRanking += rank;
            //    ranks[index] = rank;
            //}
            Parallel.For(0, generation.Length, index =>
            {
                Genome genome = generation[index];
                double rank = target.CalculateFitness(genome.Genes);

                totalRanking += rank;
                ranks[index] = rank;
            });

            // Sort the ranks
            sortingStrategy.Sort(generation, ranks);

            return totalRanking;
        }

        #endregion // Helpers
    }
}